package liangtWorkSpace.suanfa;

import org.w3c.dom.Node;

import java.util.List;
import java.util.Stack;

/**
 * 链表
 */
public class ListNode {
    public static class Node {
        public int value;
        public Node next;

        public Node(int v) {
            this.value = v;
        }
    }


    /**
     * 快慢指针
     * 获取中间点 -- 偶数获取中间前的一个点
     */
    public static Node midOrUpMinNode(Node node) {
        //如果节点只有一个或两个则直接返回Node
        if (node == null || node.next == null || node.next.next == null) {
            return node;
        }
        // 如果节点大于等于3则运算节点位置
        Node slow = node.next;
        Node fast = node.next.next;

        /* 循环遍历 -- 获取最新节点 */
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * 判断是否是回文链表
     *
     * @param node
     * @return
     */
    public static boolean isPalindrome1(Node node) {
        Stack<Node> stack = new Stack<>();

        Node cur = node;

        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }

        while (node != null) {
            if (node.value != stack.pop().value) {
                return false;
            }
            node = node.next;
        }
        return true;
    }

    /**
     * 判断是否是回文链表 2 不创建新的空间
     *
     * @param node
     * @return
     */
    public static boolean isPalindrome2(Node node) {
        return true;
    }

    /**
     * 逆转链表
     * 1-> 2-> 3-> 4
     * 1 2 3
     *
     * 1 <- 2  3-> 4
     * 1    2  3
     *
     * 1 <- 2  3-> 4
     *      12 3
     *      1  23
     *      1  2  3
     * 1 <- 2<-3   4
     *      1  2   3
     *         12  3
     *         1   23
     * 1 <- 2<-3 <-4   null
     *         1   2   3
     *             12  3
     *             1   23
     * @return n1
     */
    public static Node revers(Node node){
        Node n1 = node;
        Node n2 = node.next;
        Node n3 = null;
        n1.next = null;
        while (n2 != null){
            n3 = n2.next;
            n2.next = n1;
            n1 = n2;
            n2 = n3;
        }
        return n1;
    }

    /**
     * 给定指定数字，大于数字在左，小于数字在右等于在中间
     * @return
     */
    public static Node mid(Node node,int value){
        Node sH = null;
        Node sT = null;
        Node mH = null;
        Node mT = null;
        Node bH = null;
        Node bT = null;
        Node ss = null;

        while (node != null){
            ss = node.next;
            node.next =null;
            if (node.value < value ){
                //如果小域区域 不存在则头尾指向同一个
                if (sH == null){
                    sH = node;
                    sT = node;
                }else {
                    sT.next = node;
                    sT = node;
                }
                //如果等于区域 不存在则头尾指向同一个
            }else if (node.value == value){
                if(mH == null){
                    mH = node;
                    mT = node;
                }else {
                    mT.next = node;
                    mT = node;
                }
                //如果大于区域 不存在则头尾指向同一个
            }else {
                if (bH == null){
                    bH = node;
                    bT = node;
                }else {
                    bT.next = node;
                    bT = node;
                }
            }
            node = ss;
        }

        if ( sT!= null){
            sT.next = mH;
            // 如果等于区域的尾存在则使用等于区域的尾，反之的将小于区域的尾赋值尾等于区域
            mT = mT == null ? sT:mT;
        }
        if(mT != null){
            mT.next = bH;
        }
        // 从小到大遍历，如果小头存在则返回小头，反之返回等头，最后返回大头
        return sH != null ? sH : (mH != null ? mH : bH);
    }



    public static void prinf(Node node){
        Node n = node;
        while ( n != null){
            System.out.print( n.value + ",");
            n =  n.next;
        }
    }

    public static void main(String[] args) {
        Node head = new Node(0);
        Node node = head;

        for (int i = 1; i < 5; i++) {
            Node a = new Node(i);
            node.next = a;
            node = a;
        }

        node = head;
        System.out.println("原始链表！");
        prinf(node);
        Node nodeRever = revers(head);
        System.out.println("逆序");
        prinf(nodeRever);

        nodeRever = mid(nodeRever,2);
        System.out.println("打印区域划分之后的链表");
        prinf(nodeRever);
    }


}
